/**
 * Created with Intellij JDEA
 * Description:
 * User:
 * Date:2022-06-09
 * Time:14:38
 */
public class 背包问题 {
    public static int backPackII(int m, int[] a, int[] v) {
        int len = a.length;
        if(m == 0 || len == 0) {
            return 0;
        }
        int[][] dp = new int[len + 1][m + 1];
        for(int i =0;i < len + 1;i++) {
            dp[i][0] = 0;
        }
        for(int i = 0;i < m + 1;i++) {
            dp[0][i] = 0;
        }
        for(int i = 1;i < len+1;i++) {
            for(int j = 1;j < m+1;j++) {
                if(a[i-1] <= j) {
                    int count = dp[i-1][j - a[i-1]] + v[i-1];
                    dp[i][j] = Math.max(count, dp[i-1][j]);
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[len][m];
    }
}
